//a^n算法：n >= 0  O(logn)
//把n分解成二进制，一次次右移
int power1(int a, int n)
{
    int pow = 1;
    int p = a;
    while ( 0 < n ) {
        //末位是0，就跳过
        if ( n & 1 )//最后一位是1
        {
            //末位是1，把当前权（几次方）添加进来
            pow *= p;
        }
        n >>= 1;
        p *= p;//最后一位是0，不断增加对应位的权（次方）a的 2 4 8 16 次方
    }
    return pow;
}
//a ^ 3 = 11 = 2 + 1
//a ^ 7 = 111 = 4 + 2 + 1
//a ^ 15 = 1111 = 8 + 4 + 2 + 1
